% \documentclass{article}
% \usepackage{amsthm}
% \usepackage{amssymb}
% \usepackage{graphicx}
% 
% \newcommand{\bproof}{\begin{proof}}
% \newcommand{\eproof}{\end{proof} \vspace{20pt}}

% <3 SEXINESS
% \theoremstyle{plain}% default
% \newtheorem{thm}{Theorem}[section]
% \newtheorem{lem}[thm]{Lemma}
% \newtheorem{prop}[thm]{Proposition}
% \newtheorem*{cor}{Corollary}
% \theoremstyle{definition}
% \newtheorem{defn}{Definition}[section]
% \newtheorem{conj}{Conjecture}[section]
% \newtheorem{exmp}{Example}[section]
% \theoremstyle{remark}
% \newtheorem*{rem}{Remark}
% \newtheorem*{note}{Note}
% \newtheorem{case}{Case}

% \begin{document}

\section{Theorems and Conjectures}
\label{sec:theorems-and-conjectures}

%\subsection{Value to to an Edge}

\begin{thm}
 \label{dropthm}
For any graph $G$, let $\alpha_{-}^{m}$ be the lowest $\alpha$ at which any node will drop some number of edges on the multi-drop model and let $\alpha_{-}^s$ be the same for the single drop model. $\alpha_{+}^m$ is the highest $\alpha$ at which an edge will be added in the multi-drop model and $\alpha_{+}^s$ is same for the single drop model. $\alpha_{-}^m \leq \alpha_{-}^s$, but $\alpha_{+}^m = \alpha_{+}^s$

\begin{proof} ($\alpha_{-}^m \leq \alpha_{-}^s$) An edge that will drop in the standard model when cost is $\widehat{\alpha}$ will still drop in multi-drop, because a node in multi-drop may drop any one edge as its move. So $\alpha_{-}^m \not{>} \alpha_{-}^s$. However, $\alpha_{-}^m$ can be less than $\alpha_{-}^s$ because for some G there are $\alpha$ at which a node will drop more than one edge, but not drop only one. An example of this is the line of three nodes, $a$, $b$, and $c$. $u(a)=u(c)=\frac{1}{2}-\alpha$ and $u(b)=\frac{2}{2} + \frac{1}{3} - 2\alpha$. ${\Delta}v_{-{a,b}}(a) = {\Delta}v_{-{a,b}}(b) = \frac{5}{6}$ and likewise for the ${b,c}$ edge. However, ${\Delta}v_{-{a,b},{b,c}}(b) = \frac{2}{3}$. Therefore the lowest $\alpha$ from drops will be lower on the multi-drop model.
\end{proof}
\begin{proof}
Proof ($\alpha_{+}^m = \alpha_{+}^s$): In both models only one edge can be added per move, so for creating edges the models are identical. Therefore: $\alpha_{+}^m = \alpha_{+}^s$.
\end{proof}
\end{thm}

\begin{thm}
\label{equalvaluetheorem}

Given two disconnected components $A$ and $B$ and two nodes $a \in A$ and $b \in B$, if $a$ and $b$ become connected by the edge $e = (a, b)$, they have equal changes in utility.

\bproof
All the pairs $(i, j)$ where $i$ and $j$ are in $A$ have shortest paths unaffected by the addition of $e$. This is true because if any of the shortest paths from $i$ to $j$ start to use $e$, they will have to cross into the component $B$ and then return by the same edge $e$ into $A$ to reach their destination. Since no shortest path will every contain such a cycle, these pairs shortest paths are not affected. Likewise for $k$ and $l$ both in $B$.

Before $e$ is added, all of $a$'s and $b$'s value comes from their membership in shortest pairs between some $i$ and $j$ or $k$ and $l$ respectively. After $e$ is added, $a$ and $b$ get some value from every pair of nodes $i \in A$ and $k \in B$ because all of these pairs' shortest paths must pass through $e$ depositing equally into $a$ and $b$. Since every pair of nodes in the graph is accounted for, and the only ones that change when $e$ is added give value equally to $a$ and $b$, their changes in utility are equal.
\eproof
\end{thm}


\begin{cor}
\label{equalvaluecor}
Given two components $A$ and $B$ that are connected only by the two nodes $a \in A$ and $b \in B$, if the edge between them $e = (a, b)$ is removed, they have equal changes in utility.

\bproof
Since the utility change from adding an edge is the same as the utility change from removing the edge, this claim is exactly symmetrical to Theorem \ref{equalvaluetheorem}.
\eproof
\end{cor}


\begin{defn}
\label{edgevaluedefn}

Consider the edge $e = (a, b)$. If $e$ were removed, it would cause a change in value to $a$ and a change in value to $b$. Let the value of $e$, $v_e$, be the lesser of these two changes. $v_e$ then represents the largest cost at which both nodes would agree to add $e$. 

\end{defn}


\begin{lem}
\label{bridgelem}
For any graph $G$ on $n$ nodes, either there exists two subgraphs $A$ and $B$ that would be disconnected by the removal of some edge $\langle{}a,b\rangle{}$ where $a \in A$ and $b \in B$ or not.

\bproof

Consider the case where no such $A$ and $B$ exist. Consider an arbitrary edge $e={\langle}a,b{\rangle}$. Define $A'$ so that $a \in A'$ and any neighbor of $A'$ that is not $b$ is in $A'$. Clearly $A'$ is a connected subgraph. Let $B'$ contain all nodes not in $A'$. $B'$ is also a connected subgraph. $A'$ and $B'$ partition all of the nodes. Let $K$ be all of the edges from a node in $A$ to a node $B$ not including $e$. The value of $e$, $v_{e}$, will be greater or equal on $\langle V, E - K \rangle$ than on $G$.

Consider all $i \in A'$ and all $j \in B'$. On $G$, $a$ gets value from the $i, j$ pair or it does not.

First consider when $a$ does not gain any value from the pair on G. On G' $i$ and $j$ are still connected, but now their shortest paths must pass through $a$, so $a$ now gets some value from the $i, j$ pair. Therefore the value of $a$ has increased for these nodes.

If $a$ got value from the $i, j$ pair on G then it will get equal or more value on G'. If $a$ got value from the $i, j$ pair on G then there was at least one shortest path from $i$ to $j$ that contained $a$. All shortest paths from $i$ to $j$ had to contain $b$ because if they did not then, by the definition of $A$, $A$ would contain $j$, which is a contradiction. $a$ and $b$ are adjacent on all shortest paths that contain $a$, because otherwise the path would not be a shortest path. Additionally these paths do not cross from $A$ to $B$ on any edge other than $e$, because all other edges from $A$ to $B$ are incident to $b$ and visiting $b$ twice will not occur on a shortest path.

All shortest paths on $G$ from $i$ to $j$ that did not contain $a$ will no longer be paths on $G'$ since all edges from $A$ to $B$ that did not contain $a$ do not exist on $G'$. All shortest paths that contained $a$ on $G$ will remain shortest paths on $G'$ because all edges that are only in $A$ or only in $B$ are unchanged and the paths only cross from $A$ to $B$ on $e$. Therefore the value of $a$ that comes from these pairs can only increase or remain the same on $G'$. The same argument applies to $b$. Since the values of $a$ and $b$ both increased or remained the same. $v_{e}$ on $G'$ is greater than or equal to $v_{e}$ on $G$.
\eproof
\end{lem}


\begin{thm}
\label{maxedgevaluethm}

Given any network $N$ on $n$ nodes and the definition of edge value from Definition \ref{edgevaluedefn}, the edge $e = (a, b)$ has a value

$$v_e \leq \frac{n - 2}{3} + \frac{(\frac{n}{2}-1)^2}{4} + \frac{1}{2}$$

\bproof

It is sufficient to find the highest possible value that any edge can have in any graph on $n$ nodes.

Any graph on $n$ nodes takes one of the following two forms:

\begin{enumerate}
\item Two components $A$ and $B$ that are disconnected except for the edge $e = (a, b)$ with $a \in A$ and $b \in B$.
\item Two components $A$ and $B$ that are connected only by the edge $e = (a, b)$ with $a \in A$ and $b \in B$ and the set of edges $K$ where every edge in $K$ connects a node in $A$ to a node in $B$.
\end{enumerate}

By Lemma \ref{bridgelem}, whichever graph on $n$ nodes has the highest valued edge will be a graph of the first type. Since the graph is of this type, the change in $a$'s value due to $e$ is the same as the change in $b$'s value due to $e$. (Theorem \ref{equalvaluetheorem})

Let $P_{i,j}$ be the set of nodes in all the shortest paths from node $i$ to node $j$. Then, the value of $e$ is given by the following sum:

$$\sum_{i \in A, j \in B}{\frac{1}{|P_{i,j}|}}$$

In order to maximize this quantity, we need to minimize the cardinality of $P_{i,j}$ for every pair $i \in A$ and $j \in B$. Consider the pair $a$ and $b$. $P_{a,b}$ is size 2 due to $e$, and can be no smaller. For every pair between $i \neq a$ and $b$, the size of $P_{i,b}$ can be no smaller than 3. Likewise for pairs between $j \neq b$ and $a$. Pairs between $i \neq a$ and $j \neq b$ can have $P_{i,j}$ no smaller than 4. All of these limits are achieved when it is true that for all $i$ in $A \backslash \{a\}$ the shortest path between $i$ and $a$ is length 1, and that for all $j$ in $B \backslash \{b\}$ the shortest path between $j$ and $b$ is length 1.

For example, a satisfying structure is a pair of stars of sizes $a$ and $n - a$ connected by the center. We know that the value of the edge between the center of two stars is given by

$$v_{\star \star} = \frac{a - 1}{3} + \frac{(a - 1)(n-a-1)}{4} + \frac{n-a-1}{3} + \frac{1}{2}$$

We would like to know the value of $a$ that would maximize this value. So, we will take the derivative with respect to $a$:

\begin{eqnarray*}
 \frac{\partial v_{\star \star}}{\partial a} & = & \frac{1}{3} + \frac{n - a - 1 - (a - 1)}{4} - \frac{1}{3} \\
 & = & \frac{n - 2a}{4} = 0 \\
\end{eqnarray*}

So there is a maximum or minimum at $a = \frac{n}{2}$. We should compare the edge value for this $a$ and for the bounds of $a$: $a = 1$ and $a = n - 1$.

When $a = \frac{n}{2}$, $v_{\star \star} = \frac{n^2}{16} + \frac{n}{12} + \frac{1}{12}$.

When $a = 1$, $v_{\star \star} = \frac{n}{3} - \frac{1}{6}$. Likewise for $a = n - 1$. So, for all $n > 2$, $a = \frac{n}{2}$ is the highest edge value.

This happens when the size of $A$ is the same as the size of $B$. The value of $v_{\star \star}$ in this case is equal to the claimed maximum $v_e$.
\eproof
\end{thm}


\begin{thm}
\label{densitythm}
  For all $n\geq16$, we can produce a graphs for density ranges $0 < d < \frac{n}{4}$, $\frac{n}{2} \leq d < \frac{n}{2}$, $\frac{n}{2} \leq d < \frac{3n}{4}$, and $\frac{3n}{4} \leq d < n-1$.
\begin{proof}
 First, we know we can construct the empty graph with density 0 for any $n$ and the complete graph with density $n-1$ for any $n$, so we need really focus on the other ranges.

$0 < d < \frac{n}{4}$ We know that for $n\geq8$, $\frac{n}{4} = 2$, so a star, which has density $\frac{n-1+n}{n}=\frac{2n-1}{n}$ just under 2 and is always stable, will work to satisfy this range.

$ \frac{n}{4} \leq d < \frac{n}{2}$ The $1$-hedgehog has density $\frac{n^2+ 4}{4n}$ just over $\frac{n}{4}$ and works to satisfy this range for any $n\geq 8$.

$\frac{n}{2} \leq d < \frac{3n}{4}$ The $k$-single-tail on $k=\frac{n}{4}$ tail nodes has density $\frac{9n}{16}-{1}{4}$, which is over $\frac{1}{2}$ for all $n>4$. It also has a range of stability for all applicable $n\geq16$. %\todo{Make this explicit!}

$\frac{3n}{4} \leq d < n$ A complete graph on $n-1$ nodes with a single tail - the $k$-single-tail on $k=1$ tail nodes - has density $\frac{n^2-3n+4}{n}$ essentially just under $n$ and a stable range of $\alpha$ for all $n\geq 5$. %\todo{Make this explicit!}

So, within the defined ranges, we can always produce a graph for a big enough $n$.
\end{proof}
\end{thm}


\begin{fcon}
  On any graph, the node with the highest value $v$ is also the one with the highest value from being an endpoint $v_E$.

\emph{Counterexample:}
A graph on which this is not the case is given in figure \ref{fig:v_vs_ve}.

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[normalnode/.append style={minimum size=5mm},
    focusnode/.append style={minimum size=5mm}]
    
    \node [normalnode] (1) {};
    \node [normalnode,below=of 1] (2) {};
    \node [normalnode,below=of 2] (3) {};
    \node [normalnode,below left=of 3] (4) {};
    \node [focusnode,above left=of 4] (5) {};
    
    \node [normalnode,above=of 5] (11) {};
    \node [normalnode,left=of 5] (6) {};
    \node [normalnode,above=of 6,left=of 11] (10) {};
    
    \node [normalnode,above=of 10] (12) {};
    \node [normalnode,above=of 11,right=of 12] (13) {};
    
    \node [normalnode,below left=of 6] (7) {};
    \node [normalnode,above left=of 7] (8) {};
    \node [normalnode,left=of 10, above=of 8] (9) {};
    
    \draw (1) -- (2) -- (3) -- (4) -- (5) -- (11) -- (13) -- (12) -- (10)
      -- (11);
    \draw (13) -- (10) -- (6) -- (5);
    
    \draw (6) -- (7) -- (8) -- (9) -- (10);
    \draw (6) -- (8) -- (10);
    \draw (6) -- (9) -- (7) -- (10);
  \end{tikzpicture}
  \caption{A graph whose highest-valued node is not the node with the highest value from being an endpoint.\label{fig:v_vs_ve}}
\end{figure}

\end{fcon}

\begin{fcon}
  \label{connectivity}
  A disconnected graph $G=(V,E),|E|\geq1$ is unstable for all $\alpha$.
\emph{Counterexample:} \\
The graph in figure \ref{fig:stable_disconnected} is stable and disconnected.

\begin{figure}
  \centering
  \begin{tikzpicture}[node distance=3mm and 3mm]
    \foreach \i in {0,...,9}
    {
      \path (90+36*\i:2cm) node (\i) [normalnode] {};
    }
    \path (0:4cm) node (loner) [focusnode] {};
    \draw (0) -- (1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --
      (8) -- (9) -- (0);
  \end{tikzpicture}
  \caption{A stable, disconnected graph}
  \label{fig:stable_disconnected}
\end{figure}
\end{fcon}

\begin{con}
\label{conjendpt2}
  On a stable graph, the node with the highest value $v$ is also the one with the highest value from being an endpoint $v_E$.
\begin{note}
 This claim is certainly true for all stable graphs on $n\leq6$ node graphs. Also, it is true for stars, rings, complete graphs, 1-hedgehogs, and lines.
\end{note}

\end{con}

\begin{con}

\label{conjendpt1}
  In a connected component $C$, the node with the highest value from begin an \emph{endpoint} in shortest paths $v_E$ is the node that will gather most value from connecting to another component.
\begin{note}
 This is true for the specific special structures we consider in our discussions of $\omega$ and $Psi$.
\end{note}
\begin{note}
 Consider the nodes $u$ and $v$ s.t. $v_E(u) > v_E(v)$. We would like to show that $u$ forms a more valuable edge with any other arbitrary component $\hat{C}$ that $v$.
\begin{equation}
 \sum_{all i \in C\backslash{u,v}}{\frac{1}{P_{u,i}}} > \sum_{all i \in C\backslash{u,v}}{\frac{1}{P_{v,i}}}
\end{equation}
Then, it is necessary to show that, \emph{due to structural constraints that govern the actual values}, the following statement is true (not that it is \emph{certainly not} true in general without further restrictions):
\begin{equation}
 \sum_{all i \in C\backslash{u,v}}{\frac{1}{P_{u,i}+c} }> \sum_{all i \in C\backslash{u,v}}{\frac{1}{P_{v,i}+c}}
\end{equation}
where $c$ is the length of any additional path formed from any node in some component $\hat{C}$ 

Only then will we be able to say that for any new path formed, $u$ is a preferable middleman over $v$.
\end{note}
\end{con}
% \end{document}
